package debtbundler.domain.bll.solver;

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.logging.Level;
import java.util.logging.Logger;

import debtbundler.domain.entity.Debt;
import debtbundler.domain.entity.Person;
import debtbundler.domain.entity.impl.EntityManager;
import debtbundler.mathematics.Combinations;
import debtbundler.mathematics.GaussianLinSysSolver;
import debtbundler.mathematics.MatrixToString;

public class LinearSystemSolver extends SolverSkeleton {
	private static Logger logger = Logger.getLogger(LinearSystemSolver.class.getName());
	
	private double[][] A;
	private double[] b;
	private double[] bestSolution; // The best solution, i.e. the one with the least number of non-zero debt values. 
	private int numFreeVar; // The number of free variables in the current full linear equation system for the debts. 
	private int numMostZeros = 0; // The number of zero debts in a the currently known best solution
	int[] removedColIndices = null; // column indexes (= variables) that were removed from the original to get the best solution. If null, no columns were removed because the solution to the original system was unique. 
	
	/**
	 * Solves debts between given persons.

	 * @param persons	persons whose debts to calculate
	 */	
	public LinearSystemSolver(Collection<Person> persons) {
		solve(persons);
	}

	/**
	 * Backbone of the solution algorithm.
	 * <p>
	 * We form a linear system Ax = b. When there are d debtors and c creditors, 
	 * the size of solution x is (d*c)*1 and x[c*i + j] is the value of the debt owed 
	 * by debtor i to creditor j.
	 * <p>
	 * Elements of b are balances of the debtors (positive) and creditors (negative)
	 * with the following correspondence:
	 * <p>
	 * b[0]: first debtor <br>
	 * ... <br>
	 * b[debtors.size()-1]: last debtor <br>
	 * b[debtors.size()] = first creditor <br>
	 * ... <br>
	 * b[b.length-1] = last creditor <br>
	 * <p>
	 * The coefficient matrix A is constructed so that for each debtor i, we have equation
	 * where total value of debts to paid by i equals i's balance:<br>
	 * x[c*i] + x[c*i + 1] + ... + x[c*i + c] = b[i] <br>
	 * Coefficients for other elements of x are zero. <br>
	 * For each creditor j, we must have equation where the total value of debts received by j
	 * equals i's balance:<br>
	 * -x[c*i] - x[c*i + 1] - ... -x[c*i + c] = b[i] <br>
	 * Coefficients for other elements of x are zero. <br>
	 * <p>
	 * Thus, the size of the coefficient matrix A is (d+c)*(d*c).
	 * Rows of A indexed between [0, d-1] represent the debtors in the order 
	 * of <code>debtors</code> list. Rows of A indexed between [d, d+c-1] 
	 * represent the creditor in the order of <code>creditors</code> 
	 * list. Values of A are -1, 0, or 1: <br>
	 * 	-1: the person corresponding to the row is the creditor of the debt <br>
	 *	 0: = the person is neither the debtor nor the creditor in the debt <br>
	 * 	 1: the person is the debtor of the debt <br>  
	 * <p>
	 * This linear system is solved by Gaussian elimination. It is possible that it has no
	 * unique solution. In that case we determine which one of them has the greatest number
	 * of zero valued debts, translating to the the fewest number of transactions between 
	 * persons to resolve the debts.
	 */
	@Override
	protected void calculateSolution() {
		createMatrix();
		determineBestSolution();
		createDebts();
	}
		
	private void createMatrix() {
		int d = debtors.size();
		int c = creditors.size();
				
		// Form the RHS vector: first debtors in the list's order, then the creditors
		b = new double[d + c];
		int idx = 0;
		for (Person debtor : debtors) {
			b[idx] = debtor.getBalance();
			++idx;
		}	
		for (Person creditor : creditors) {
			b[idx] = creditor.getBalance();
			++idx;
		}
		
		// Form the coefficient matrix matching the RHS vector
		A = new double[d+c][d*c];
		// Coefficients of equations "sum of debts paid by debtor's = sum debtors balance"    
		for (int i = 0; i < d; ++i) {
			for (int j = i*c; j < (i+1)*c; ++j) {
				A[i][j] = 1;
			}
		}
		// Coefficients of equations "negative sum debts received by creditor = sum creditors credit" 
		for (int i = d; i < c+d; ++i) {
			for (int j = (i-d); j < d*c; j += c) {
				A[i][j] = -1;
			}
		}	
	}	
		
	private void determineBestSolution() {
		
		// Solve once to determine the number of free variables in the system
		GaussianLinSysSolver linSysSolver = new debtbundler.mathematics.GaussianLinSysSolver(A, b);
		this.numFreeVar = linSysSolver.getNumberOfFreeVariables();
		double[] solutionVector = linSysSolver.getSolutionVector();
		
		logger.log(Level.FINER, "Solved the full system.\nFree variables = {0}, a solution is {1}.", new Object[]{numFreeVar, MatrixToString.toString(solutionVector)});
		
		if (solutionVector == null) { 
			throw new IllegalStateException("Could not find solution");
		} else if (isValid(solutionVector)) {
			this.bestSolution = solutionVector;
			this.numMostZeros = countZeros(bestSolution);
			
			logger.log(Level.FINER, "Initial solution is valid, has {0} zeros", numMostZeros);
		}
		
		/*
		* If there were zero free variables in the system, we already have the best solution. 
		* If not, solve the system with all combinations of free variables (= debt values) 
		* set to zero and determine which combination produces the solution with the most 
		* zeros (= best solution). 
		*/
		
		// All numFreeVar combinations of column indices. We try solving all the systems with free variables 
		// fixed to zero by setting their coefficients to zero.
		int[][] colIdxCombsToZero = Combinations.getCombinationIndices( new Object[linSysSolver.getSolutionVector().length], numFreeVar ); 

		if (numFreeVar > 0) {
			
			// Go through all combinations of indices of columns to remove.
			for (int combIndex=0; combIndex < colIdxCombsToZero.length; ++combIndex) {
				 
				// Create a set of the columns to zero in this step
				Set<Integer> colIdxToZero = new LinkedHashSet<Integer>();
				for (int j = 0; j < colIdxCombsToZero[combIndex].length; ++j) {
					colIdxToZero.add(colIdxCombsToZero[combIndex][j]);
				}
				
				// Copy the original coefficient matrix so that coefficients for the chosen free variables are zeroed
				double[][] Amod = new double[A.length][A[0].length];
				for (int colIdx = 0; colIdx < A[0].length; ++colIdx) {
					if (!colIdxToZero.contains(colIdx)) {
						for (int rowIdx = 0; rowIdx < Amod.length; ++rowIdx) { 
							Amod[rowIdx][colIdx] = A[rowIdx][colIdx];
						}
					} else {
						for (int rowIdx = 0; rowIdx < Amod.length; ++rowIdx) { 
							Amod[rowIdx][colIdx] = 0;
						}
					}
				}
				
				logger.log(Level.FINER, "Solving reduced system with debts {0} zeroed", colIdxToZero);

				// Solve the reduced system and check if the solution got any better (more zeros)
				linSysSolver = new debtbundler.mathematics.GaussianLinSysSolver(Amod, b);
				solutionVector = linSysSolver.getSolutionVector();

				if (isValid(solutionVector)) {
					int zeroCount = countZeros(solutionVector);
					logger.log(Level.FINER, "Found valid solution {0}, has {1} zeros", new Object[]{MatrixToString.toString(solutionVector), zeroCount});
					
					if (zeroCount > this.numMostZeros) { 
						this.bestSolution = solutionVector;
						this.numMostZeros = zeroCount;
						
						logger.log(Level.FINER, "Found solution {0} is currently the best solution", MatrixToString.toString(solutionVector));
					}
					
				} else {
					logger.log(Level.FINER, "Found solution {0}, not valid", MatrixToString.toString(solutionVector));
				}

			}
			
		}
		
		if (this.bestSolution == null) {
			throw new IllegalStateException("Could not find solution");
		}
		
	}


	/**
	 * Checks the validity of the debt solution vector. It's valid if it's not null
	 * and all the elements are non-negative
	 * 
	 * @param solutionVector
	 * 	the debt solution vector
	 * @return
	 * 	<code>true</code>, if the solution is valid
	 * 	
	 */
	private static boolean isValid(double[] debtSolutionVector) {
		
		if (debtSolutionVector == null) {
			return false;
		}
		
		for (int i=0; i<debtSolutionVector.length; ++i) {
			if (debtSolutionVector[i] < 0) {
				return false;
			}
		}
		
		return true;
	}

	/**
	 * Counts the number of elements valued equal to zero in 
	 * the given array.
	 * 
	 * @param array
	 * 	the array
	 * @return
	 * 	the number of zero valued elements in the array
	 */
	private static int countZeros(double[] array) {
		int zeroCount = 0;
		for (int i=0; i<array.length; ++i) {
			if (array[i] == 0) {
				zeroCount++;
			}
		}
		return zeroCount;
	}	

	/**
	 * Creates debt objects out of the solution.
	 * 
	 */
	private void createDebts() {
		
		debts = new ArrayList<Debt>();
		
		for (int debtIndex=0; debtIndex < bestSolution.length; ++debtIndex) {
			if (bestSolution[debtIndex] != 0) {
				
				int debtorIndex = (int)Math.floor(debtIndex/this.creditors.size());
				int creditorIndex = debtIndex - this.creditors.size()*debtorIndex;
				
				Debt debt = EntityManager.createDebt( debtors.get(debtorIndex), creditors.get(creditorIndex) );
				debt.setValue(bestSolution[debtIndex]);
				debts.add(debt);
					
			}
		}
	}	
}
